%-----------------------------------------------------------------------------
%
%               Template for LaTeX Class/Style File
%
% Name:         sigplanconf-template.tex
% Purpose:      A template for sigplanconf.cls, which is a LaTeX 2e class
%               file for SIGPLAN conference proceedings.
%
% Author:       Paul C. Anagnostopoulos
%               Windfall Software
%               978 371-2316
%               paul@windfall.com
%
% Created:      15 February 2005
%
%-----------------------------------------------------------------------------


\documentclass[preprint,natbib]{sigplanconf}

\usepackage{amsmath}
\usepackage{listings}


\lstdefinelanguage{Scala}{% 
       morekeywords={% 
                try, catch, throw, private, public, protected, import, package, implicit, final, package, trait, type, class, val, def, var, if, this, else, extends, with, while, new, abstract, object, requires, case, match, sealed,override},% 
         sensitive=t, % 
   morecomment=[s]{/*}{*/},morecomment=[l]{\//},% 
   escapeinside={/*\%}{*/},%
   rangeprefix= /*< ,rangesuffix= >*/,%
   morestring=[d]{"}% 
 }
 
\lstdefinelanguage{Haskell}{%
   otherkeywords={=>},%
   morekeywords={abstype,break,class,case,data,deriving,do,else,if,instance,newtype,of,return,then,where},%
   sensitive,%
   morecomment=[l]--,%
   morecomment=[n]{\{-}{-\}},%
   morestring=[b]"%
  }
  
%  numberbychapter=false,
\lstset{breaklines=true,language=Scala} 
%\lstset{basicstyle=\footnotesize\ttfamily, breaklines=true, language=scala, tabsize=2, columns=fixed, mathescape=false,includerangemarker=false}
% thank you, Burak 
% (lstset tweaking stolen from
% http://lampsvn.epfl.ch/svn-repos/scala/scala/branches/typestate/docs/tstate-report/datasway.tex)
\lstset{
    xleftmargin=1em,%
    frame=single,%  TODO REMOVE only for floating listings
    captionpos=b,%
    fontadjust=true,%
    columns=[c]fixed,%
    keepspaces=true,%
    basewidth={0.56em, 0.52em},%
    tabsize=2,%
    basicstyle=\renewcommand{\baselinestretch}{0.97}\small\tt,% \small\tt
    commentstyle=\textit,%
    keywordstyle=\bfseries,%
}









\begin{document}

\conferenceinfo{WXYZ '05}{date, City.} 
\copyrightyear{2008} 
\copyrightdata{[to be supplied]} 

\titlebanner{banner above paper title}        % These are ignored unless
\preprintfooter{short description of paper}   % 'preprint' option specified.

\title{Scrapping boilerplate in Scala: Experience report}
%\subtitle{Subtitle Text, if any}

\authorinfo{Jelle Pelfrene}
           {Katholieke Universiteit Leuven, Belgium}
           {jelle.pelfrene@student.kuleuven.be}
%\authorinfo{Name2\and Name3}
%           {Affiliation2/3}
%           {Email2/3}

\maketitle

\begin{abstract}
Scala is a hybrid object-oriented functional language on the Java Virtual
Machine. Scala aims to be concise, but even though usage of higher-order
functions is standard idioms, some other versions of boilerplate code remain
hard to remove.

One such example is code that deals with naming and variable binding. We have
implemented a small System F interpreter in Scala using nominal abstract
syntax. This generates quite a lot of simple but tedious boilerplate code.
We have ported the type reification scheme the Scrap your boilerplate,
Reloaded to Scala and use that to scrap our nameplate. We investigate whether
this really made our code smaller and more clear.


\end{abstract}



\section{Introduction}
Over the last years the Haskell language has been the proving ground for
research in datatype-generic programming: more general abstraction over types
than is now known in languages such as Java as `generic programming'. This
technique can be used for eliminating different kinds of code repetition or
boilerplate code, as well as writing more flexible code.

The verbosity and inflexibility of the Java language seems to be a principal
reason for the recent popularity of dynamic languages such as Ruby. They
generally pay much attention to the ``don't repeat yourself'' principle, but
sacrifice all type safety to get concise code and higher-order methods.

The Scala language is a recent language on the Java Virtual Machine that
couples functional to object-oriented programming within a strong typesystem.
It can access the normal classfile based reflection mechanisms of the JVM.
 We
have investigated in what degree datatype-generic techniques can contribute to
making Scala code as concise and flexible as possible, while using the
structured technique instead of direct reflection.

Datatype-generic programming promises
\begin{itemize}
  \item less boilerplate code
  \item greater resilience against changes
  \item greater reuse
  \item clearer code
\end{itemize}
and these are all properties that programmers who traded up from Java to Scala
are interested in.

As a case study, we have implement a simple System F interpreter
in Scala using Nominal Abstract Syntax .
Then we use the ValSpine  type reification method to
structure the use of polymorphic functions with reflection.
We applied this method to scrap the naming plate, using the structured
reflection in both cases.

Finally we evaluate the effectiveness of the followed approach.

\section{The Scala Language}
The Scala language, designed by Martin Odersky, is an
effort to create a non-pure multi-paradigm scalable language by joining the
Object-Oriented and Functional programming styles. The language is designed to
be scalable by using the same core abstractions for both very small programs and big systems. The core abstractions are
derived by comparing and unifying Object-Oriented and Functional design practices.  
Scala aims to be a general purpose language, interoperable with Java
and positioned as a gradual step up from Java.


Scala has a static type system with partial local type inference. Scala compiles
to bytecode for the Java Virtual Machine or the Common Language Runtime, using
type erasure like the Java Generics implementation so only the outer type is
remembered at runtime.




\subsection{Unification of functions and objects}
Scala is fully Object-Oriented, so every value is an object. The call mechanism
is method invocation on objects, with dynamic dispatch on the receiver object.
Scala is also Functional in that it has function values and higher-order
methods. This is implemented by making the `function' concept also an object.
The type of functions from A to B is written \texttt{A $\Rightarrow$ B}, but
this is purely syntactic sugar for the type \texttt{Function1[A,B]}. Function
application to an argument is performed as a
method call of the
\lstinline[language=Scala]{def apply( arg:A) :B}
 method.
 

A polymorphic method uses explicit annotation of its type parameters in Scala as
opposed to Haskell, so an external method that takes the head element of a list
argument would be rendered as 
\lstinline[language=Scala]{def first[E]( list: List[E]):E}

However, in datatype-generic programming we frequently use rank two
polymorphic functions.. Scala has no notion such as the \texttt{forall a .}
like in Haskell, though it is possible to emulate it using the Scala implementation of
structural subtyping. Using this, a parameter's type can be declared as an
inline sum of the needed structures. Given the syntactic correspondence between
function application and the presence of an \texttt{apply} method, we can then
write method declarations such as
\begin{lstlisting}[frame=none, language=Scala]
 def applypolytransform[A]( polyfun: { def apply[T](t:T):T } , arg:A) : A 
\end{lstlisting}

Pattern matching is also present in Scala. A pattern match block is an object
of type \texttt{PartialFunction} that also has a method \texttt{isDefinedAt}

In the same way this can be extended structurally to a polymorphic analogue.




\subsection{Using implicits to model type classes}

 Scala also
has user-defined implicit parameters which we can use for an almost literal translation of type classes.

A formal parameter of a method can be made implicit by preceding it with the
keyword\texttt{implicit}. This method can then be called both normally and without actually providing the missing argument. If the argument
corresponding to the implicit parameter is missing in a call, the compiler will
automatically try and find a suitable value and pass it behind the
scenes. Suitable values are marked as being available for use by the compiler
as stand-ins by preceding their declaration with the same keyword
\texttt{implicit}. The compiler will look up all such declared implicit
values within the static scope of the call-side. If there is a single best
conforming instance, this will be statically added to the method call. If
there is no suitable stand-in value in scope, or there are multiple options generating 
ambiguity, the compiler willl emit a warning.

This mechanism coupled to functional-style traits, which take all methods
arguments instead of dispatching on a \texttt{this} object,  can be used to
emulate Haskell typeclasses. A trait implements the method dictionary symbolized 
by the type class declaration. All necessary functionality is left as deferred methods, while
default implementation are layered on the former just like in non-implicit
trait.
This way an analogue to the type class \texttt{Ord} can be written as trait
\texttt{Ordering}
\begin{lstlisting}[float, language=Scala,caption=functional-style Ordering]
trait Ordering[T] extends PartialOrdering[T] { 
  def compare(x: T, y: T): Int
  override def lteq(x: T, y: T): Boolean = compare(x, y) <= 0
  override def gteq(x: T, y: T): Boolean = compare(x, y) >= 0
  override def lt(x: T, y: T): Boolean = compare(x, y) < 0
  override def gt(x: T, y: T): Boolean = compare(x, y) > 0
  override def equiv(x: T, y: T): Boolean = compare(x, y) == 0
}
\end{lstlisting}
The syntax of type constraints is then replaced by writing an ad-hoc generic
method as taking an implicit parameter of the method dictionary type:
\lstinline[language=Scala]
{ def sort[T](list:List[T])(implicit ord:Ordering[T]):List[T] }
This is almost a literal transcription of the Object-Oriented design pattern of
using an external `strategy'.
\begin{lstlisting}[float,label=ordered, caption = object-oriented style Ordered]
trait Ordered[A] {
  def compare(that: A): Int

  def <  (that: A): Boolean = (this compare that) <  0
  def >  (that: A): Boolean = (this compare that) >  0
  def <= (that: A): Boolean = (this compare that) <= 0
  def >= (that: A): Boolean = (this compare that) >= 0
  def compareTo(that: A): Int = compare(that)
}

\end{lstlisting} 
Another, arguably more authentic Object-Oriented, approach
using a dispatching style such as the \texttt{Ordered} trait, is also
possible using a variation called implicit conversions. Now we demand a conversion function as implicit parameter:
\lstinline[language=Scala]
{def sort[T](list:List[T])(implicit ord: T=>Ordered[T]):List[T] }. This usage
makes an `open classes' approach possible. The advantage is we now get
greater flexibility couple to the same dispatching
style as when requiring traditional inheritance of the trait as in 
\lstinline[language=Scala]{def sort[T <: Ordered[T]](list:List[T]) }.








\section{Scrap your boilerplate reloaded in Scala}


A later version of the Scrap your boilerplate
approach exposes a structural view of a value as what 
is called the spine view. The spine view basically exposes a case class 
as a constructor function applied to a set of values. The function
 application here is now reified as data, 
and one can write transforming functions somewhat like folds over the spine of the value.




For every type we now need a reified type representer or converter named TypeMan 
(Type in the original paper). Such a converter knows how to convert a 
value of the proper type into that value's structural spine representation. 
\begin{lstlisting}[language=Scala]
  //contains function concrete => structural for datatype
  //specific for each datatype
  trait TypeMan[A]{  //kind: *=>*
    def toValSpine(a:A):ValSpine[A]
  }
\end{lstlisting}
This type converter then implements one part of the view 
between nominal and structural representations of a value.
The other direction is implemented by the datatype for the structural representation itself:
\begin{lstlisting}[language=Scala]
  //structural view of constructor application to values
  //contains function structural => concrete for datatype: structural info is enough to to this
  sealed trait ValSpine[A] { //stages in constructing a value
    def buildFromSpine:A
  }
\end{lstlisting}

The spine view itself mixes the arguments of the constructor call together
with a partial application of the constructing function into a single list-like
structure. This spine structure reifies the partially applied constructor
function. The spine view consists of two case classes: a ConstrExt case denoting a whole value, and a Apped case containing a parameter as head and a tail, so we can operate using pattern matching.
\begin{lstlisting}[language=Scala]
  type ConstrDesc = {val n:String} //extra info: name
  case class ConstrExt[A](a:A,desc:ConstrDesc) extends ValSpine[A] {
    def buildFromSpine = a
  }
  case class Apped[A,B](constred: ValSpine[A=>B] , a_ :Typed[A]) extends ValSpine[B] {
    def buildFromSpine = constred.buildFromSpine (a_._1)
  }

  case class Typed[A](value:A,typerep:TypeMan[A]) extends Tuple2[A,  TypeMan[A]](value,typerep)
\end{lstlisting}

Because we are attempting to work polymorphically, we need to carry a
representation of the type structure together with a value. The head of an
Apped case contains not just the value, but a ``Typed'', a tuple of the value and the specific type converter that handles the value. 

The way a spine value can turn itself back into a nominal version is not too difficult.
The ConstrExt case reifies a fully applied constructor method: 
it contains the resulting nominal value and can just return it.
In the Apped case the object contains one subelement of the class within its Typed, 
as well as a structural representation of the already partially applied 
rest of the constructor. 
It can transform the structural constructor back into an actual 
constructor function and feed that function the constructor parameter it carries.

All structural behaviour is then implemented by first fetching the structural 
representation of a value of type T using its type converter TypeMan[T].
Then you operate on this structural view in whatever way is wanted, and finally 
the modified structural representation of type ValSpine[T] can transform itself back into a T.


The middle part of such a transformation, that performs the changes on the 
structural spine of the value, is implemented as a pattern of 
two corecursive functions.

In the simplest queries, a function on nominal types just dispatches to a second 
function that performs a fold on the structural representation of the value.
A small example that calculates the number of subelements a case class has, 
can demonstrate the way a fold over the spine is expressed.
\begin{lstlisting}
  def arity[T](t:T)(implicit tman:TypeMan[T]):Int = arityprim(tman.toValSpine(t))
  def arityprim[T](sp:ValSpine[T]):Int = sp match {
    case ConstrExt(a,desc) => 0
    case Apped(f, Typed(x,t)) => arityprim(f)+1
  }
\end{lstlisting}

Another example (listing \ref{sumexample} ) exhibits the full typical corecursive structure, 
to count the sum of integers at any level within a value.
\begin{lstlisting}[float,label=sumexample,caption=generic deep sum]
  def sum[A](a:A)(implicit tman:TypeMan[A]):Int = tman match {
      case IntMan => a
      case _    => sumstructural (tman.toValSpine(a))
  }
  def sumstructural[B](s:ValSpine[B]):Int = s match {
      case ConstrExt(c,i) => 0
      case Apped(f, Typed(x,t)) => sumstructural(f) + sum(x)(t)
  }
\end{lstlisting}
Here we see in the function for normal types, how ad-hoc behaviour can be 
defined by pattern matching on the type representer to decide the type of
the value the function is applied to. This works because there are some
predefined instances IntMan, StringMan and so on.

So the pattern consists of two functions. A first one takes normal
values and either catches specific behaviour or redirects to the
second one structural behaviour. A second one handles the structural spines.
The structural function returns a default value in the case of a fully applied
value, and else performs an operation
on the result of a deeper structural call and the result of the first function
on the actual subelement. It is for this last call that we need to keep the
TypeMan of the constructor parameter.


The boilerplate needed to enable this pattern is a version of TypeMan per datatype 
you want to traverse.
If we could get this information inside 
the class file for all values, this syntactic overhead of carrying the
representation explicitly could be eliminated, just like with ordinary
reflection the class file of a value can be accessed at all times. As it is we
carry the representation along.



The instances of TypeMan can of course be written explicitly for each datatype. 
However, this follows a rigid template and could be automated. Ideally a
compiler plugin would generate an automatic instance for a case class. 
Until Scala compiler plugins are viable, it is easier to use a set of helper 
functions that generate a TypeMan instance for a case class.
\begin{lstlisting}[language=Scala]
  def CaseClass1ToValSpine[T,Param1]
      (clazz:Class[T])(implicit p1tyman: TypeMan[Param1]) :TypeMan[T]
  def CaseClass2ToValSpine[T,Param1,Param2]
      (clazz:Class[T])(implicit p1tyman: TypeMan[Param1], 
        p2tyman:TypeMan[Param2]):TypeMan[T]
  ...
\end{lstlisting}
The TypeMans that result from these functions construct ValSpines based on the primary 
constructor of the case class gathered by reflection on the class file.
Notice that we also have to pass a context explicitly, because of the way
 JVM reflection deals with nested classes. This way providing a TypeMan instance
 costs just one line of enabling boilerplate code.

\begin{lstlisting}[language=Scala, float, caption=Generating a TypeMan based on the primary constructor through reflection]
def CaseClass1ToValSpineWithEnv[T<:Product,Param1]
  (env:Object)(clazz:Class[T])(implicit p1tyman: TypeMan[Param1]) :TypeMan[T] = {
  implicit def ToProduct1(t:T):Product1[Param1] = {
    val asproduct = t.asInstanceOf[Product]
    assume (asproduct.productArity == 1, "CaseClass1ToValSpine received a product of wrong arity")
    val param1ok: Param1 = asproduct.productElement(0).asInstanceOf[Param1] 
    new Tuple1[Param1](asproduct.productElement(0).asInstanceOf[Param1])
  } 
  
  val constr = clazz.getDeclaredConstructors()(0)
  new TypeMan[T]{
   def toValSpine(t:T) = 
    {val constrf = (p1:Param1)=>constr.newInstance(
           {val arr=new Array[Object](2);
            arr(0)=env;arr(1)=p1.asInstanceOf[Object];arr})
           .asInstanceOf[T]
     val p1wrapped = Typed( t ._1, p1tyman)
     Apped(ConstrExt(constrf, new {val n = clazz.getName()})
          , p1wrapped)
                           }
    val classname = clazz.getName
    override def toString():String = classname
    }
}

\end{lstlisting}


\section{Casestudy: scrap your nameplate}

We will document how the 
Then we will try to scrap the boilerplate code this technique requires, using
the structural spines from ``Scrap your boilerplate, reloaded'', roughly guided
by the Functional Pearl ``Scrap your nameplate''
demonstrating such a process in Haskell. 

\subsection{nominal abstract syntax}
Dealing with variable names, correct capture-avoiding substitution and
equivalence up to renaming is a notoriously tricky subject to get right.
Over time, a lot of different options have been explored. Options include
first-order abstract syntax with explicit substitution boilerplate; name-free
approaches such as the DeBruijn indices used in ``Types and Programming
Language'' by Pierce, and higher-order abstract syntax
which reuses the variable and binding system of the meta-language.
Because of increased interest in elegant solutions to this problem, related to
the popularity of machine-checked proofs, and the wish to have such proofs resemble
a natural style, a new ecosystem of ``Nominal'' logics and abstract syntax has
been developed. The theoretic principles were developed in by Pitts
 and implemented in a number of languages.
A recent Functional Pearl paper  ``scrap your nameplate"
explains how to port the approach as a library to Haskell.



\subsubsection{structure of nominal abstract syntax}
Nominal abstract syntax introduces names as a separate first-class entity, and
bindings as a datatype encapsulating a binding name and an expression where
this name is in scope, written here name//body .
The insight behind nominal abstract syntax
is the use of reversible
swapping of names instead of replacement of one name by another as a mechanism
of renaming. An invertible swapping operation that exchanges two names is better
behaved than replacement. 
We define a swapping operation [a$<>$b] on a name c as follows: if c == a,
the result \texttt{c[a$<>$b]} is b, if c == b the result is a and else the
result remains c. If we perform a swapping on a binding: (name//body)[a$<>$b] the result just
propagates the swap to both elements: (name[a$<>$b]//body[a$<>$b]).

This operation preserves equality of names: if two names at different locations
are equal, and we perform the same swapping on them, the resulting names will
still be equal. But also inequality: If they are different names, the results
after swap will still be different from each other. Another property is
freshness: a name is fresh for a term if there are no unbound occurrences of
the name within the term. Again, if a name is fresh the definition of swapping
ensures the resulting name after swapping will still be fresh.

This is better behaved than replacement, because replacement only respects
equality. Indeed, if t==u: t[x:=y] == u[x:=y]. But inequality is not necessarily
maintained: if x != y then x[x:=y] == y == y[x:=y]. 
And substitution can also change a name from fresh to not fresh :  x is not free in $\lambda$ x. f x y;
 but x[x:=y] == x is free 
in ($\lambda$ x. f x y)[x:=y] == ($\lambda$ x1. f x1 y)).

The concepts that must be implemented are the following:
\begin{itemize}
  \item names
  \item a name-binder that couples a name to a term in scope, and for which
  alpha-equivalence coincides with equality.
  \item a swapping operation on expressions, that switches between two names
  \item a freshness operation on expressions, false if the name occurs free
  \item a name generation mechanism that can generate fresh names 
\end{itemize}

Just like for the swapping operation, the freshness and equality rules are
defined in the paper and quite easy to implement.
A name is fresh to another name if they are different. It is also always fresh
to primitive that contains no names. Freshness on a composite term is the
conjunction of freshness on the subterms. Lastly, a name is fresh on a binding
if it is equal to the bound name(because all occurences then are bound and not
free) or if the name is different, if it is fresh to the bound name and to the
term in scope.

The equality on bindings should be defined so that, when the bindings share the
same bound name, they are equal if the bodies are equal. Lastly, and this is
the only tricky case: if the names of the bindings are different (a//t vs b//u),
the bindings are equal when the the name of the first binding is fresh to the
body of the second (a fresh to b), and the body of the first is equal to the
body of the second one with both bound names swapped (t equal to u[a$<>$b]).
\\
Capture avoiding substitution is then defined on top of these definitions as
follows, using ``var(name)'' for a syntax node that refers to a bound name:
\begin{itemize}
  \item var(a)[a:= P] == P
  \item var(b)[a:= P] == var(b)
  \item (b//body) [a:= P] == b//body2 if b fresh to P and body[a:= P] == body2 
\end{itemize}
For a composite structure, the result of substitution is reached by simply
passing the substitution on to the children nodes.

The case for substitution on a binder is only specified if the binding variable
is fresh to the structure being substituted for the name. To implement this
algorithm, we must make sure this is always the case. This is easy if we have
the traditional endless source of new names fresh to the entire environment.
When we want to perform substitution an a binding, we generate a totally new
name and use the swap operation between the old binding name and the new name
on the body of the binding. The new binding so derived is alpha-equivalent to
the original one (this procedure performs exactly the steps to make the above
definition for alpha-equivalence true) and since the new name is new to the
system it is fresh to the structure being substituted.
\\
One extra operation is the ``support'' of a structure, a list of all the free
variables that occur within. Having easy access to the support helps to
implement the check on existentially quantified variables exiting their scope.


\subsubsection{conventional implementation of nominal abstract syntax}
Following the structure of the scrap your nameplate paper, we introduce the
following interfaces \texttt{Nominal} and \texttt{CanSubstIn} to our Scala
implementation., together with a class \texttt{Name} and \texttt{Binds}
synonymous to the \texttt{\\} syntax
\begin{lstlisting}
trait Nominal[Self] {
  def swap(a: Name, b: Name): Self
  def fresh(a: Name): Boolean
  def supp: List[Name]
}
trait CanSubstIn[SubstParam, Self] { 
  def subst(sub: Name => Option[SubstParam]): Self
}
\end{lstlisting}
Both names and bindings are \texttt{Nominal}, and since most of the rules of
abstract nominal syntax have to do with these cases, these can be nicely
packaged away as a library.The definition of \texttt{CanSubstIn} allows its use
as an infix type constructor.

\begin{lstlisting}
class Name(val name: String) extends Nominal[Name] {
  def swap(a: Name, b: Name) = if(this == a) b else if(this == b) a else this
  def fresh(a: Name) = this != a
  def supp = List(this)
  ...
}
type Binds[x] = \\[x]
class \\[T](private val binder: Name, private val body: T)(
            implicit val bodynom: T => Nominal[T]) extends Nominal[\\[T]] {

  def unabs: (Name, T) = { val newBinder = Name(binder);  
                             (newBinder, body swap (binder, newBinder)) }

  def swap(a: Name, b: Name) = \\(binder swap(a, b), body swap(a, b)) // boilerplate
  def fresh(a: Name) = if(a == binder) true else body fresh (a)
  def supp = body.supp filter (_ != binder)
  ...  
}
\end{lstlisting}

We then model the nodes of our abstract syntax tree as case classes (see listing
\ref{syntaxtree}) in straightforward correspondence to the grammar of SystemF
\begin{lstlisting}[float, label=syntaxtree,caption=abstract syntax tree]
trait AbstractSyntax  {
sealed trait LTerm 
case class Var(n: Name) extends LTerm
//takes a term parameter
case class Lam(ty: LType, body: \\[LTerm] extends LTerm
case class App(funt:LTerm, argt:LTerm) extends LTerm
//takes a type parameter
case class TLam(body: \\[LTerm]) extends LTerm
...

sealed trait LType extends LTerm
case class TyBool() extends LType
case class TyUniv(body: \\[LType]) extends LType
}
\end{lstlisting}


Because the methods in a \texttt{Binds} depend on those in its body, and in System F 
we have abstractions that bind LTerms and abstractions that bind
LTypes, we need to make both LTerm and LType \texttt{Nominal}. We can do this
just by making LTerm inherit \texttt{Nominal[LTerm]} and likewise for LType.
Then in each nodetype we have to implement the three methods, according to the
trivial rules for composite datastructures. This needs three lines of
boilerplate code per node in the abstract syntax tree. We can catch the
identical cases for all the leaf nodes by subtyping, so this alone saves us
quite a bit of boilerplate. All in all we need about 60 lines of user-written
code for these trivial definitions.


Of course this \texttt{Nominal} framework will serve to implement
substitution. Implementing substitution takes again some code on the library
side for names and binders, but the code on the user side is now not homogenous
anymore. We have to deal with the pattern for composite structures which is
straightforward, as well as the specific behaviour for variables.
Using inheritance to specify \texttt{CanSubstIn} would be ideal, but then LTerm
needs to be declared \texttt{LTerm extends Nominal[LTerm] with (LTerm
CanSubstIn LTerm) with (LType CanSubstIn LTerm)}, since terms contain
abstraction over terms and types. Scala unfortunately not allow inheriting from
the same trait twice with different type parameters. The solution is to use
implicit conversions.

In our substitution interface, the arguments are decorated with a specific
instance of \texttt{CanSubstIn},based on the combination of the type of the
substitution and the type of the element that is substituted. So we implement
three different implicit conversions with their own substitution function:
\texttt{LTermTakesLTypeParam(t)}, \texttt{LTermTakesLTermParam(t)} and
\texttt{LTypeTakesLTypeParam(t)}. Each leads to a substitution function that
pattern matches on the case class and performs the substitution logic, either
applying the substitution in case of a variable or redirecting to the library
code in case of a binding. 
In this library code for bindings 
we need to manually partially apply a type parameter, so a call looks a bit unwieldy:
\texttt{(new AbsTakesSubstitution[LTerm]).AbsIsSubstable(t)
         (LTermTakesLTermParam).subst(sub) }

 Or in the majority of cases where we have an
ordinary non-leaf class, distributing the substitution function over the
children (using the same implicit conversions to make them substitutable).
This
leads to about 90 lines of boilerplate code.

The code as a whole is rather clean, with the interesting cases mostly in fixed
library implementations and a lot of boilerplate code on the user side. It is
this boilerplate we aim to remove next. 



\subsection{Generic \texttt{Nominal}}
The ``scrap your nameplate'' approach tackles automatic definition of
\texttt{Nominal} by implementing it as a derivable type class. 
As there is as of
yet no compile-time system for derivable type classes in Scala, everything will
be done at runtime through reflection. 
\\
Because the elements of \texttt{Nominal} can be derived purely structurally,
they can also be implemented using well-behaved corecursive functions
over the typespine of a value.
The code that implements \texttt{fresh} is given in listing
\ref{freshname_listing}.In the non-structural function we specifically capture
cases where an inherited implementation is available to dispatch to the
cases for names and bindings. We then need to provide the implicit conversions
\texttt{LTerm => Nominal[LTerm]} and \texttt{LType => Nominal[LType]}.

\begin{lstlisting}[language=Scala,float,label=freshname_listing,caption=datatype-generic \texttt{fresh}] 
def freshname[T](a:Name)(t:T)(implicit tman: TypeMan[T]):Boolean =  t match 
  { case inheritancetrumps: Nominal[T] => inheritancetrumps.fresh(a) 
    case _ => freshname_gen(tman.toValSpine(t))(a)}
  }
  def freshname_gen[T](ts:ValSpine[T])(a:Name):Boolean = ts match {
      case ConstrExt(_,_) => true
      case Apped(deep,Typed(arg,innertman))=> freshname(a)(arg)(innertman) && freshname_gen(deep)(a)
  }
\end{lstlisting}

Using the library class \texttt{GenNominal} we can implement the implicit
conversion as in listing \ref{termtonominalconv}. The specific implicit conversion 
is the place to specify cases that should not happen generically through the spineview.
\begin{lstlisting}[language=Scala,float,label=termtonominalconv,caption=Layering \texttt{Nominal}]
implicit def LTerm2Nominal(arg:LTerm):Nominal[LTerm] = new GenNominal[LTerm](arg) {
  override def fresh(a:Name) = arg match 
    { case special:Record => special.fresh(a)
      case _ => super.fresh(a)
    }
  override def swap(a:Name,b:Name) = arg match {
    case special: Record => special.swap(a,b)
    case _ => super.swap(a,b)
  }
  override def supp:List[Name] = arg match {
    case special:Record => special.supp
    case _ => super.supp
  }}


  //use to layer nominal on spineview
  class GenNominal[Self]( val self:Self)(implicit val tyman:TypeMan[Self]) extends Nominal[Self]{
    assume (tyman != null, "creating gennominal with tyman null: "+self)
    def swap(a: Name, b: Name): Self = (swapnames_gen(tyman.toValSpine(self))(a,b)).buildFromSpine
    def fresh(a: Name):Boolean  = freshname_gen(tyman.toValSpine(self))(a)
    def supp: List[Name] = suppnames_gen(tyman.toValSpine(self))
  }
\end{lstlisting}
One such implicit conversion for \texttt{LTerm} and one for \texttt{LType} 
together mean almost 30 lines user-written code.

But to enable such generic operations on the spine of values, there must be 
instances of \texttt{TypeMan}, to convert a value to its spine representation.
Creating these \texttt{TypeMan}s through reflection as explained 
previously 
takes 
14 
lines, 
one for each case class. We also need to add a TypeMan for 
\texttt{Binds[LTerm]} and one for \texttt{Binds[LType]} because these as
subelements within the nodes modelling abstraction, and
the TypeMan for a node depends on the TypeMan instances for its subnodes. For these two instances, the TypeMan inherits 
from a library-provided PrimitiveTypeMan. The TypeMans will not really be used 
because of the exception clause seen in listing \ref{freshname_listing}

This last reason also applies to all the case classes who's children are 
declared as \texttt{LTerm} or \texttt{LType}. We need a \texttt{TypeMan} for those
classes up in the hierarchy.
These are also the \texttt{TypeMan} instances that the call to \texttt{GenNominal} requires.
These have to be implemented by manually pattern matching on the argument and 
redirecting to the proper TypeMan implementation, as listing \ref{typetypemandispatcher} demonstrates. 
The two dispatchers 
come to an 
additional 
25 lines of boilerplate.

\begin{lstlisting}[language=Scala,float,label=typetypemandispatcher,caption=dispatching function for LType]
//dispatcher
implicit object LTypeTypeMan extends TypeMan[LType] {
        def toValSpine(t:LType):ValSpine[LType] = t match {
                case x:BaseType => new sybrevolutions.forvalues.PrimitiveTypeMan(x.name).toValSpine(x)

                case x:TyVar => TyVarTypeMan.toValSpine(x)
                case x:TyArr => TyArrTypeMan.toValSpine(x)
                case x:TyUniv => TyUnivTypeMan.toValSpine(x)
                case x:TyExist => TyExistTypeMan.toValSpine(x)
}}
\end{lstlisting}


\subsection{Generic substitution}

The structure of substitution is conceptually a bit harder than that of \texttt{Nominal}
The base cases of the inductive definition are now variable references, names and bindings.

We still need three versions of \texttt{CanSubstIn}: \texttt{LType CanSubstIn LType}, 
\texttt{LType CanSubstIn LTerm} and \texttt{LTerm CanSubstIn LTerm}.

We again implement the functionality using mutually recursive functions over the structural spine of a value.
We need two such sets of functions: one function that for \texttt{LTerm} into \texttt{LTerm}, 
and one for \texttt{LType} into anything. 

The full code for performing term into term substitution can be seen in listing \ref{termintotermsubstable}.
When the function \texttt{subst}is initially called from the substitution interface, 
it is always to operate on a term. Therefore the value is joined 
with a reference to the typeMan[LTerm] and the flow continues to the specific function. 
The specific function captures some exceptional cases,variables and the general 
case through ordinary pattern matching on the incoming value. Because a pattern match 
is an object of type \texttt{PartialFunction}, it is possible to write 
combinators such as \texttt{Except} and \texttt{orElse} that lift ordinary 
PartialFunctions into a polymorphic variation. This way we can create the 
more complicated behaviour of this function as a composition.
\begin{lstlisting}[language=Scala]
trait PartialPolyFunction1 {
  def isDefinedAt[T](t:T):Boolean
  def apply[T](t:T):T
  def orElse(second:PartialPolyFunction1) = new HigherToLowerPrecedencePartialPolyFunction1(this,second)
}
\end{lstlisting}
The same exception for records as in \texttt{Nominal} is joined here by a shortcut \texttt{LType}.
We encounter such nodes in this specific function because the structural function 
applies it to all of the subelements, also types, in cases such as the node for function abstraction.
The pattern match on bindings happens differently from all the others, by 
pattern matching on the type representation value. If we use 
a normal typetest, type erasure on the JVM doesn't differentiate between a 
\texttt{Binds[LTerm]} and a \texttt{Binds[LType]}.

\begin{lstlisting}[language=Scala,float,label=termintotermsubstable,caption=performing a term substiution on a term]
class TermintoTermSubstable(self:LTerm) extends (LTerm CanSubstIn LTerm) {
  def subst(sub: Name => Option[LTerm]): LTerm 
    = { specificSubstituteWithTerm[LTerm](sub, self)(findTermManhere) }
      
  //function that gets called on children:
  // if a variable => perform substitution
  // if a binds => perform substitution
  // special behaviour => through exception clause
  // anything else => convert to valspine
  def specificSubstituteWithTerm[T](sub: substitution[LTerm], t:T)
                                     (implicit tman:TypeMan[T]):T = {
     //first any exceptions
     val excclauses = Except [Any] { 
         case r@Record(fields) => 
           Record(fields.map( {case (lbl,term) => 
 (lbl, specificSubstituteWithTerm[LTerm](sub,term)(findTermManhere)) }))
         case typ:LType => typ // because ltypes do not take lterms
     }
     //then we get the variable case 
     val variableclause = Except[Any] {
         case dis @RefersByName(n) => (sub(n)).getOrElse(dis)
     } 
     //then the redirect to the general cases
     val general = Except[T] {
         case general =>
         GenericLTermIntoTSubst(tman.toValSpine(general),sub).buildFromSpine
     }
     val combined = excclauses orElse variableclause orElse general
     
    tman match {
       case TypeManDefs.BindsTermTypeMan => 
              (new AbsTakesSubstitution[LTerm]).AbsIsSubstable(t)
              (LTermTakesLTermParam).subst(sub)
       case _   => combined[T](t)
  }}
      
  def GenericLTermIntoTSubst[T](vs:ValSpine[T], sub: substitution[LTerm]):ValSpine[T] = vs match{
     case c@ConstrExt(_,_) => c
     case Apped(deep,Typed(arg,argtman)) => { 
        implicit val findTMan = argtman
        val argmod = specificSubstituteWithTerm(sub,arg)
        Apped(GenericLTermIntoTSubst(deep,sub), Typed(argmod,argtman)) 
}}}
\end{lstlisting}
Besides the syntax for combinator polymorphic partial functions, 
I have also added an interface RefersByName and a 
companion extractor object that allows matching both variable 
nodes, \texttt{Var} and \texttt{TyVar}, using the same syntax.
\begin{lstlisting}[language=Scala]
object RefersByName {
  def unapply(ref:RefersByName):Option[Name] = Some(ref.getName)
}
trait RefersByName {
  def getName:Name
}
\end{lstlisting}
This works using a recent ``extractor'' feature, where the name of an object
with an unapply method can be used in a pattern match. This way we can unify
pattern matching over variables without naming the different nodes that contain
term-level and type-level variables.


In the second function, which performs type substitution (
partially in listing \ref{partial_typesubst}), pattern matching on the \texttt{TypeMan} instead of the value is more important.
If we just wrote two dynamic typetests here to distinguish 
\texttt{Binds[LTerm]} from \texttt{Binds[LType]} ,type erasure would always 
cause the first match to succeed. In ordinary programming on the JVM this is
something you either have to live with 
or work around by implementing specific identification methods like ``bindsTerm()'' and ``bindsType()''.
This would destroy the opportunity for a single parametric \texttt{Binds[T]}.
Because our \texttt{TypeMan}s contain 
full type information, we can escape the erasure problem here.

\begin{lstlisting}[language=Scala,float,label=partial_typesubst,caption=fragment of type substitution]
//we would like to write
case body:Binds[LTerm] => (new AbsSubstTo[LType]).AbsIsSubstable(body)(LTermTakesLTypeParam).subst(sub)
case body:Binds[LType] => (new AbsSubstTo[LType]).AbsIsSubstable(body)(LTypeTakesLTypeParam).subst(sub)
//without full type information from TypeMan we have to write
case binding:Binds[LTerm] =>  try {
      (new AbsSubstTo[LType]).AbsIsSubstable(binding)(LTermTakesLTypeParam).subst(sub).asInstanceOf[T]
   } catch { case e:ClassCastException =>  t match{
        case binding:Binds[LType] => (new AbsSubstTo[LType]).AbsIsSubstable(binding)(LTypeTakesLTypeParam).subst(sub).asInstanceOf[T] }
   }
}

//using TypeMan we now write
tman match {
  case TypeManDefs.BindsTermTypeMan => 
    (new AbsTakesSubstitution[LType]).AbsIsSubstable(t)(LTermTakesLTypeParam).subst(sub)
  case TypeManDefs.BindsTypeTypeMan =>
     (new AbsTakesSubstitution[LType]).AbsIsSubstable(t)(LTypeTakesLTypeParam).subst(sub)
   case _   =>  combined[T](t) 
}
\end{lstlisting}



Every user of a library in this style must extend it by writing his own substitution functions, 
composed from library code and the \texttt{TypeMan} pattern.

In the substitution functions itself we now count around 70 lines of code.



% \subsubsection{Using type manifests}
% In the current implementation the instances of the type converters are generated 
% based on the class file. 
% For now the class file is accessed by getting it from the experimental manifest
% typing feature. This is an experimental type reification feature that exposes
% just the class file for now.
% When we pass this classfile into the converter generator for case
% classes, we must also pass the correct type parameters.
% This is because the class file itself, due to type erasure, is not
% enough to know which other type convertors it depends on. 
% However, in the future the manifest typing feature should expose this, and then the single lines of boilerplate can disappear.
% 
% 
% %\subsubsection{problems/modifications}
% %One of the major differences one runs into is between adts in haskell and case
% %class hierarchies in scala. The effect of an adt in haskell in like having a
% %name for the type Either<caseclass1,Either<caseclass2,\ldots
% %Because the top name is a type too, we need to implement dispatchers.
% 

\newpage
\section{Conclusions interpreter case study}

The conclusion to be drawn from the working interpreter, is that Scala is 
indeed expressive enough to enable a limited form of datatype-generic
programming.

Datatype-generic programming promised
\begin{itemize}
  \item less boilerplate code
  \item greater resilience against changes
  \item greater reuse
  \item clearer code
\end{itemize}

Our traditional implementation of Nominal Abstract Syntax had quite a bit of
code bloat.  We need around 60 lines to implement the \texttt{Nominal} base functionality, with another 90 to layer 
substitution on top. And that is with only rather trivial code remaining on the 
user's side, with the tricky rules already  implemented as a library.

By using the ``Scrap your boilerplate, Reloaded'' generic mechanism, we need 30 
lines to implement \texttt{Nominal} generically, and around 70 to implement substitution.
However, this methods requires \texttt{TypeMan} boilerplate code by itself, which comes to another 40 lines.

Hence there is a small reduction in code size, but not a significant one. However, already now 
the cost of providing the \texttt{TypeMan}s is amortized over two features. 
I believe that in a more featureful interpreter or compiler, the code reduction
versus the baseline would be more pronounced.
\\
The code has become more resilient to changes. To add or remove nodes would require only the corresponding modification of the \texttt{TypeMan} instances.
If the new datatypes need exceptional treatment, there are clear locations where those exceptions can be specified.
\\
The library parts are now reusable. This is more a matter of adding the abstractions 
by transferring to Nominal Abstract Syntax from DeBruijn. Modelling names 
and bindings as classes instead of convention centralizes and moduralizes
the code. We didn't even need advanced abstraction mechanisms, just the right
abstractions.
\\
Finally, although reading more abstract code takes some getting used to, the code now indeed expresses the intention more clearly. 
This is an effect of modularization by splitting the decisions and the traversal logic apart.
The code is a lot more structured than if everything had been written directly to the ordinary JVM reflection API. 
\\
\\
\subsubsection*{Possible enhancements}
Further conciseness is possible by integrating the type reification mechanism of 
\texttt{TypeMan} with the standard class files, or with another representation 
without type erasure. Then the implementation could also become more type-safe.

The general structural functions could be made more conspicous by providing default abstractions for common patterns.

The use of manually dispatching functions should be made redundant 
by auto-generating them for sealed case class hierarchies that correspond to abstract data types.











%\appendix
%\section{Appendix Title}
%
%This is the text of the appendix, if you need one.
%
%\acks
%
%Acknowledgments, if needed.



\bibliographystyle{plainnat}

\begin{thebibliography}{}

@techreport{ScalaOverview,
		author = "Martin Odersky and Philippe Altherr and Vincent Cremet and Iulian Dragos and Gilles Dubochet and Burak Emir and Sean McDirmid and Stéphane Micheloud and Nikolay Mihaylov and Michel Schinz and Erik Stenman and Lex Spoon and Matthias Zenger",
		title = {An {O}verview of the {S}cala {P}rogramming {L}anguage},
		institution = "{\'{E}}cole {P}olytechnique {F}{\'{e}}d{\'{e}}rale de Lausanne (EPFL)",
		number = "LAMP-REPORT-2006-001", 
		year = 2006  
		}



@Article{SYB1,
  author    = "Ralf L{\"a}mmel and Simon {Peyton Jones}",
  title     = "Scrap your boilerplate:
               a practical design pattern for generic programming",
  journal   = "ACM SIG{\-}PLAN Notices",
  publisher = "ACM Press",
  volume    = "38",
  number    = "3",
  pages     = "26--37",
  month     = mar,
  year      = "2003",
  note      = "Proceedings of the ACM SIGPLAN Workshop
               on Types in Language Design and Implementation (TLDI~2003)"
}



@inproceedings{SYBreloaded,
  author = "Ralf Hinze, Andres Loeh, and Bruno C. d. S. Oliveira",
  booktitle = "Functional and Logic Programming (FLOPS 2006)",
  editor = "Philip Wadler and Masami Hagiya",
  location = "Fuji Susono, Japan",
  month = "April",
  title = {"Scrap Your Boilerplate" Reloaded},
  url = "http://people.cs.uu.nl/andres/SYB0.html",
  year = "2006",
}
@inproceedings{SYnameplate,
 author = {James Cheney},
 title = {Scrap your nameplate: (functional pearl)},
 booktitle = {ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming},
 year = {2005},
 isbn = {1-59593-064-7},
 pages = {180--191},
 location = {Tallinn, Estonia},
 doi = {http://doi.acm.org/10.1145/1086365.1086389},
 publisher = {ACM},
 address = {New York, NY, USA},
 }




@Article{PittsAM:newaas-jv,
  author =	 {M. J. Gabbay and A. M. Pitts},
  title =	 {A New Approach to Abstract Syntax with Variable
                  Binding},
  journal =	 {Formal Aspects of Computing},
  year =	 {2001},
  volume =	 {13},
  pages =	 {341--363}
} 


@Book{TAPL,
	Title={Types and Programming Languages}, 
	Author="Benjamin C. Pierce",
	Publisher="MIT Press",
	Year=2002
	}




\end{thebibliography}

\end{document}